package com.lun.swordtowardoffer2.c02;

//我写的
public class NumMatrix {

	private int[][] sums;
	
	
	public NumMatrix(int[][] matrix) {
		this.sums = new int[matrix.length][matrix[0].length];
		
		for(int i = 0; i < matrix.length; i++) {
			int currRowSum = 0;
			for(int j = 0; j < matrix[0].length; j++) {
				currRowSum += matrix[i][j];
				int aboveSum = i == 0 ? 0 : sums[i - 1][j];
				sums[i][j] = aboveSum + currRowSum;
			}
		}
		
	}
	
	public int sumRegion(int r1, int c1, int r2, int c2) {
		return sums[r2][c2] - (r1 == 0 ? 0 : sums[r1 - 1][c2]) // 
				- (c1 == 0 ? 0 : sums[r2][c1 - 1]) // 
				+ (r1 == 0 || c1 == 0 ? 0 : sums[r1 - 1][c1 - 1]);
	}
		
}

//书上写的
class NumMatrix2{
	private int[][] sums;
	
	public NumMatrix2(int[][] matrix) {
		
		//扩大一行与一列，这样可少写防数组越界代码
		this.sums = new int[matrix.length + 1][matrix[0].length + 1];
		
		for(int i = 0; i < matrix.length; i++) {
			int currRowSum = 0;
			for(int j = 0; j < matrix[0].length; j++) {
				currRowSum += matrix[i][j];
				sums[i + 1][j + 1] = sums[i][j + 1] + currRowSum;
			}
		}
	}
	
	public int sumRegion(int r1, int c1, int r2, int c2) {
		
		return sums[r2 + 1][c2 + 1] - sums[r1][c2 + 1] // 
				- sums[r2 + 1][c1] + sums[r1][c1];
	}
	
}